{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimized Maximum of Products Distributed to Any Store"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimizedMaximum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #分配给商店的最多商品的最小值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数&nbsp;<code>n</code>&nbsp;，表示有&nbsp;<code>n</code>&nbsp;间零售商店。总共有&nbsp;<code>m</code>&nbsp;种产品，每种产品的数目用一个下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>quantities</code>&nbsp;表示，其中&nbsp;<code>quantities[i]</code>&nbsp;表示第&nbsp;<code>i</code>&nbsp;种商品的数目。</p>\n",
    "\n",
    "<p>你需要将 <strong>所有商品</strong>&nbsp;分配到零售商店，并遵守这些规则：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>一间商店 <strong>至多</strong>&nbsp;只能有 <strong>一种商品</strong> ，但一间商店拥有的商品数目可以为&nbsp;<strong>任意</strong>&nbsp;件。</li>\n",
    "\t<li>分配后，每间商店都会被分配一定数目的商品（可能为 <code>0</code>&nbsp;件）。用&nbsp;<code>x</code>&nbsp;表示所有商店中分配商品数目的最大值，你希望 <code>x</code>&nbsp;越小越好。也就是说，你想 <strong>最小化</strong>&nbsp;分配给任意商店商品数目的 <strong>最大值</strong>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回最小的可能的&nbsp;<code>x</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 6, quantities = [11,6]\n",
    "<b>输出：</b>3\n",
    "<strong>解释： </strong>一种最优方案为：\n",
    "- 11 件种类为 0 的商品被分配到前 4 间商店，分配数目分别为：2，3，3，3 。\n",
    "- 6 件种类为 1 的商品被分配到另外 2 间商店，分配数目分别为：3，3 。\n",
    "分配给所有商店的最大商品数目为 max(2, 3, 3, 3, 3, 3) = 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 7, quantities = [15,10,10]\n",
    "<b>输出：</b>5\n",
    "<b>解释：</b>一种最优方案为：\n",
    "- 15 件种类为 0 的商品被分配到前 3 间商店，分配数目为：5，5，5 。\n",
    "- 10 件种类为 1 的商品被分配到接下来 2 间商店，数目为：5，5 。\n",
    "- 10 件种类为 2 的商品被分配到最后 2 间商店，数目为：5，5 。\n",
    "分配给所有商店的最大商品数目为 max(5, 5, 5, 5, 5, 5, 5) = 5 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 1, quantities = [100000]\n",
    "<b>输出：</b>100000\n",
    "<b>解释：</b>唯一一种最优方案为：\n",
    "- 所有 100000 件商品 0 都分配到唯一的商店中。\n",
    "分配给所有商店的最大商品数目为 max(100000) = 100000 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == quantities.length</code></li>\n",
    "\t<li><code>1 &lt;= m &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= quantities[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimized-maximum-of-products-distributed-to-any-store](https://leetcode.cn/problems/minimized-maximum-of-products-distributed-to-any-store/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimized-maximum-of-products-distributed-to-any-store](https://leetcode.cn/problems/minimized-maximum-of-products-distributed-to-any-store/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['6\\n[11,6]', '7\\n[15,10,10]', '1\\n[100000]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        m = len(quantities)\n",
    "        def check(x):\n",
    "            cnt = 0 \n",
    "            for i in quantities:\n",
    "                cnt += (i + x - 1) // x \n",
    "            return cnt <= n\n",
    "        #l, r = 1, max(quantities)\n",
    "        l, r = 1, 10 ** 5\n",
    "        while l < r:\n",
    "            mid = l + r >> 1 \n",
    "            if check(mid):\n",
    "                r = mid \n",
    "            else:\n",
    "                l = mid + 1 \n",
    "        return r\n",
    "\n",
    "                 \n",
    "       \n",
    "       \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        def check(num):\n",
    "            cnt = 0\n",
    "            for quantity in quantities:\n",
    "                cnt += (quantity + num - 1) // num\n",
    "            return cnt <= n\n",
    "        \n",
    "        left, right = 1, max(quantities)\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if check(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        m = len(quantities)\n",
    "\n",
    "        def check(k):\n",
    "            nn = n\n",
    "\n",
    "            for i in quantities:\n",
    "                nn -= ceil(i / k)\n",
    "                if nn < 0:\n",
    "                    return False\n",
    "            return True\n",
    "            \n",
    "        max_ = max(quantities)\n",
    "        # print([ check(i) for i in range(1, max_)])\n",
    "        index = bisect.bisect_left(range(1, max_), True, key=check)\n",
    "        return index + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        left = 0\n",
    "        right = max(quantities) + 1\n",
    "\n",
    "        while left + 1< right:\n",
    "            mid = (left + right) // 2\n",
    "            total = sum((x - 1) // mid + 1 for x in quantities)\n",
    "            if n < total:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        left = sum(quantities) // n\n",
    "        right = max(quantities)\n",
    "        ans = right\n",
    "        while left <= right:\n",
    "            cnt = n\n",
    "            mid = (left + right) // 2\n",
    "            if mid:\n",
    "                for i in quantities:\n",
    "                    while i > 0:\n",
    "                        i -= mid\n",
    "                        cnt -= 1\n",
    "                    if cnt < 0:\n",
    "                        break\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "                    ans = mid\n",
    "                    continue\n",
    "            left = mid + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        def caculateStore(quantities: List[int], mid):\n",
    "            cnt = 0\n",
    "            for quantity in quantities:\n",
    "                cnt += math.ceil(quantity / mid)\n",
    "            return cnt\n",
    "\n",
    "        left, right = 1, max(quantities)\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if caculateStore(quantities, mid) > n:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        def check(x:int)->bool:\n",
    "            a=quantities.copy()\n",
    "            m=0\n",
    "            for i in range(len(a)):\n",
    "                m+=(a[i]+x-1)//x\n",
    "            return m<=n\n",
    "\n",
    "        l,r=1,10**9\n",
    "        while l<r:\n",
    "            mid=(l+r)>>1\n",
    "            if check(mid):r=mid\n",
    "            else:l=mid+1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    #商店数目越多，任意商店的最小的最大值就越小\n",
    "    #因此，如果给定最大值，则最大值越大，所需商店就越小\n",
    "    #给定一个最大值，至少需要多少商店\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "\n",
    "        def check(target):\n",
    "            sum_=0\n",
    "            for i in quantities:\n",
    "                sum_+=(i-1)//target+1\n",
    "            if sum_<=n:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        \n",
    "        return bisect_left(range(max(sum(quantities)//n,1),max(quantities)+1),True,key=check)+max(sum(quantities)//n,1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        m = len(quantities)\n",
    "        def check(x):\n",
    "            cnt = 0 \n",
    "            for i in quantities:\n",
    "                cnt += (i + x - 1) // x \n",
    "            return cnt <= n\n",
    "        l, r = 1, max(quantities)\n",
    "        #l, r = 1, 10 ** 5\n",
    "        while l < r:\n",
    "            mid = l + r >> 1 \n",
    "            if check(mid):\n",
    "                r = mid \n",
    "            else:\n",
    "                l = mid + 1 \n",
    "        return r\n",
    "\n",
    "                 \n",
    "       \n",
    "       \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        def check(c: int) ->bool:\n",
    "            r = n\n",
    "            for q in quantities:\n",
    "                r -= math.ceil(q/c)\n",
    "                if r < 0:\n",
    "                    return False\n",
    "            return True\n",
    "        left, right = 1, max(quantities)\n",
    "        while left < right:\n",
    "            mid = (left+right) >> 1\n",
    "            if check(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid+1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        m = len(quantities)\n",
    "        def check(x):\n",
    "            cnt = 0 \n",
    "            for i in quantities:\n",
    "                cnt += (i + x - 1) // x \n",
    "            return cnt <= n\n",
    "        \n",
    "        \n",
    "        #l, r = 1, max(quantities)\n",
    "        l, r = 1, 10 ** 5\n",
    "        while l < r:\n",
    "            mid = l + r >> 1 \n",
    "            if check(mid):\n",
    "                r = mid \n",
    "            else:\n",
    "                l = mid + 1 \n",
    "        return r\n",
    "\n",
    "\n",
    "                 \n",
    "       \n",
    "       \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        m = len(quantities)\n",
    "        def check(x):\n",
    "            cnt = 0 \n",
    "            for i in quantities:\n",
    "                cnt += (i + x - 1) // x \n",
    "            return cnt <= n\n",
    "        \n",
    "        \n",
    "        l, r = 1, max(quantities)\n",
    "        #l, r = 1, 10 ** 5\n",
    "        while l < r:\n",
    "            mid = l + r >> 1 \n",
    "            if check(mid):\n",
    "                r = mid \n",
    "            else:\n",
    "                l = mid + 1 \n",
    "        return r\n",
    "\n",
    "\n",
    "                 \n",
    "       \n",
    "       \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        m = len(quantities)\n",
    "        def check(x):\n",
    "            cnt = 0 \n",
    "            for i in quantities:\n",
    "                cnt += (i + x - 1) // x \n",
    "            return cnt <= n\n",
    "        \n",
    "        \n",
    "        #l, r = 1, max(quantities)\n",
    "        l, r = 1, 10 ** 5\n",
    "        while l < r:\n",
    "            mid = l + r >> 1 \n",
    "            if check(mid):\n",
    "                r = mid \n",
    "            else:\n",
    "                l = mid + 1 \n",
    "        return r\n",
    "\n",
    "\n",
    "                 \n",
    "       \n",
    "       \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        m = len(quantities)\n",
    "        def check(x):\n",
    "            cnt = 0 \n",
    "            for i in quantities:\n",
    "                cnt += (i + x - 1) // x \n",
    "            return cnt <= n\n",
    "        l, r = 1, max(quantities)\n",
    "        #l, r = 1, 10 ** 5\n",
    "        while l < r:\n",
    "            mid = l + r >> 1 \n",
    "            if check(mid):\n",
    "                r = mid \n",
    "            else:\n",
    "                l = mid + 1 \n",
    "        return r\n",
    "\n",
    "                 \n",
    "       \n",
    "       \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "\n",
    "\n",
    "        def check(x):\n",
    "            cnt = 0\n",
    "            for q in quantities:\n",
    "                cnt += ceil(q/x)\n",
    "            \n",
    "            return cnt <= n\n",
    "        \n",
    "        i = 1\n",
    "        j = max(quantities)\n",
    "\n",
    "        while i < j -1:\n",
    "            mid = (i+j)//2\n",
    "            if check(mid):\n",
    "                j = mid\n",
    "            else:\n",
    "                i = mid + 1\n",
    "        \n",
    "        if check(i):\n",
    "            return i\n",
    "        else:\n",
    "            return j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        m = len(quantities)\n",
    "        def check(x):\n",
    "            cnt = 0 \n",
    "            for i in quantities:\n",
    "                cnt += (i + x - 1) // x \n",
    "            return cnt <= n\n",
    "        l, r = 1, max(quantities)\n",
    "        #l, r = 1, 10 ** 5\n",
    "        while l < r:\n",
    "            mid = l + r >> 1 \n",
    "            if check(mid):\n",
    "                r = mid \n",
    "            else:\n",
    "                l = mid + 1 \n",
    "        return r\n",
    "\n",
    "                 \n",
    "       \n",
    "       \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        if n==len(quantities):\n",
    "            return max(quantities)\n",
    "        if sum(quantities)<=n:\n",
    "            return 1\n",
    "        def check(x):\n",
    "            if x==0:\n",
    "                return True\n",
    "            ret=0\n",
    "            for q in quantities:\n",
    "                ret+=q//x\n",
    "                if q%x!=0:\n",
    "                    ret+=1\n",
    "            #print(x,ret,n,ret<=n)\n",
    "            return ret<=n\n",
    "        ans=bisect_left(range(100005),True,key=check)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        # 凭感觉 应该是取模或者二分的样子\n",
    "        # s = sum(quantities)\n",
    "        # m = len(quantities)\n",
    "        l = 1\n",
    "        r = max(quantities)\n",
    "        while l<=r:\n",
    "            mid = l+r>>1\n",
    "            nd  = 0\n",
    "            for q in quantities:\n",
    "                nd += (q+mid-1)//mid \n",
    "            if nd <=n:\n",
    "                r = mid-1                \n",
    "            else:\n",
    "                l=mid+1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        def check(x):\n",
    "            tot = 0\n",
    "            for y in quantities:\n",
    "                tot += (y - 1 + x)//x\n",
    "            return tot <= n\n",
    "        \n",
    "        left, right = 1, max(quantities)\n",
    "        while left <= right:\n",
    "            mid = (left + right)//2\n",
    "            if check(mid):\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        left = 1\n",
    "        right = max(quantities)\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            total = 0\n",
    "            for q in quantities:\n",
    "                total += (q + mid - 1) // mid\n",
    "            if total > n:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        l, r = 1, max(quantities)\n",
    "        while l <= r:\n",
    "            m = (l+r)//2\n",
    "            if sum(math.ceil(q/m) for q in quantities) > n:\n",
    "                l = m+1\n",
    "            else:\n",
    "                r = m-1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        def check(k):\n",
    "            check=0\n",
    "            for num in quantities:\n",
    "                check+=(num-1)//k+1\n",
    "            return check<=n\n",
    "        l,h=1,max(quantities)\n",
    "        while h>l:\n",
    "            m=(l+h)//2\n",
    "            if check(m):\n",
    "                h=m\n",
    "            else:\n",
    "                l=m+1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        if sum(quantities)<=n: return 1\n",
    "        def f(mid):\n",
    "            return sum(int((i%mid)>0) + i//mid for i in quantities)\n",
    "        l, r = 1, max(quantities)\n",
    "        while r-l>1:            \n",
    "            mid = (r+l)//2\n",
    "            if f(mid)<=n: r = mid\n",
    "            else: l = mid\n",
    "        return l if f(l)==n else r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, nums: List[int]) -> int:\n",
    "\n",
    "        l=1\n",
    "        r=max(nums)\n",
    "        def check(mid):\n",
    "            cur=0\n",
    "            for i in nums:\n",
    "                cur+=i//mid\n",
    "                if i%mid!=0:\n",
    "                    cur+=1\n",
    "            return cur<=n\n",
    "        while l<r:\n",
    "            mid=(l+r)//2\n",
    "            if check(mid):\n",
    "                r=mid\n",
    "            else:\n",
    "                l=mid+1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        left = 0\n",
    "        right = max(quantities) + 1\n",
    "        def updiv(p, s):\n",
    "            d, m = divmod(p,s)\n",
    "            return d + (1 if m else 0)\n",
    "        \n",
    "        def check(m):\n",
    "            cnt = 0\n",
    "            for q in quantities:\n",
    "                cnt += updiv(q, m)\n",
    "            return cnt > n\n",
    "        \n",
    "        while left + 1 < right:\n",
    "            mid = (left + right ) // 2\n",
    "            if check(mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "            \n",
    "        return right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        def check(x):\n",
    "            if x==0:\n",
    "                return False\n",
    "            res=0\n",
    "            for i in quantities:\n",
    "                res+=(i+x-1)//x\n",
    "            if res<=n:\n",
    "                return True\n",
    "            return False\n",
    "        return bisect_left(range(0,1000000),True,key=check)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        # 判定问题\n",
    "        def check(x: int) -> bool:\n",
    "            # 计算所需商店数量的最小值，并与商店数量进行比较\n",
    "            cnt = 0\n",
    "            for q in quantities:\n",
    "                cnt += (q - 1) // x + 1\n",
    "            return cnt <= n\n",
    "        \n",
    "        l, r = 1, max(quantities) + 1\n",
    "        # 二分查找寻找最小的使得判定问题为真的 x\n",
    "        while l < r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if check(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "\n",
    "        def check(x):\n",
    "            ans = 0\n",
    "            for q in quantities:\n",
    "                ans += math.ceil(q / x)\n",
    "            return ans <= n\n",
    "        \n",
    "        # 找的是满足结果的最小值\n",
    "\n",
    "        l = 1\n",
    "        r = max(quantities)\n",
    "        while l < r:\n",
    "            mid = l + r >> 1\n",
    "            if check(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        \n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        right = max(quantities) +1\n",
    "        left = 1\n",
    "        def check(mid):\n",
    "            count = 0\n",
    "            for i in quantities:\n",
    "                count += (i - 1) // mid + 1\n",
    "            return count <= n\n",
    "\n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if check(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        # 寻找左边界\n",
    "        m = len(quantities)\n",
    "        l = 1\n",
    "        r = max(quantities)+1\n",
    "        def f(x):\n",
    "            store = 0\n",
    "            for q in quantities:\n",
    "                store += math.ceil(q/x)\n",
    "            return store\n",
    "        while l < r:\n",
    "            mid = (l + r)//2\n",
    "            store = f(mid)\n",
    "            if store<=n: # 计算所需商店数量的最小值，并与商店数量进行比较，商店可以分配为0\n",
    "                r = mid\n",
    "            elif store>n:\n",
    "                l = mid + 1\n",
    "        return l\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        left = 0\n",
    "        right = max(quantities) + 1\n",
    "\n",
    "        while left + 1< right:\n",
    "            mid = (left + right) // 2\n",
    "            total = sum((x - 1) // mid + 1 for x in quantities)\n",
    "            if total <= n:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        left = 1\n",
    "        right = max(quantities)\n",
    "\n",
    "        def check(tar):\n",
    "            res = 0\n",
    "\n",
    "            for q in quantities:\n",
    "                res += (q + tar - 1) // tar\n",
    "\n",
    "                if res > n:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        while left < right:\n",
    "            mid = left + (right - left)// 2\n",
    "\n",
    "            if check(mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        def check(x):\n",
    "            cnt = 0\n",
    "            for q in quantities:\n",
    "                if(q % x == 0):\n",
    "                    cnt += q // x\n",
    "                else:\n",
    "                    cnt += q // x + 1\n",
    "            return cnt <= n \n",
    "        left, right = 1, max(quantities)\n",
    "        while(left <= right):\n",
    "            mid = (left + right)//2\n",
    "            if(check(mid)):\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        def check(x):\n",
    "            cnt = 0\n",
    "            for q in quantities:\n",
    "                if(q % x == 0):\n",
    "                    cnt += q // x\n",
    "                else:\n",
    "                    cnt += q // x + 1\n",
    "            return cnt <= n \n",
    "        left, right = 1, max(quantities)\n",
    "        while(left <= right):\n",
    "            mid = (left + right)//2\n",
    "            if(check(mid)):\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        left, right = 1, max(quantities)\n",
    "        while left < right:\n",
    "            mid = left + (right-left)//2\n",
    "            total = 0\n",
    "            for i in quantities:\n",
    "                if i % mid == 0:\n",
    "                    total += i//mid\n",
    "                else:\n",
    "                    total += i//mid + 1\n",
    "            print(left,mid,right,total)\n",
    "            if total > n:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid \n",
    "        \n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        def check(mid: int) -> bool:\n",
    "            cur = 0\n",
    "            for q in quantities:\n",
    "                cur += (q + mid - 1) // mid\n",
    "            return cur <= n\n",
    "        \n",
    "        l = 1\n",
    "        r = 10 ** 5\n",
    "        while l < r:\n",
    "            mid = l + r >> 1\n",
    "            if check(mid) == True:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "      def check(v):\n",
    "        cnt = 0\n",
    "        for j in quantities:\n",
    "          cnt += ceil(j/v)\n",
    "          if cnt > n:\n",
    "            return False\n",
    "        return True\n",
    "      mx = max(quantities)\n",
    "      l = ceil(mx/n)\n",
    "      r = mx \n",
    "      return bisect_left(range(l,r+1),True,key=check)+l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        def check(x):\n",
    "            if x==0:\n",
    "                return False\n",
    "            res=0\n",
    "            for i in quantities:\n",
    "                res+=(i+x-1)//x\n",
    "            return res<=n\n",
    "        return bisect_left(range(0,1000000),True,key=check)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        def check(x):\n",
    "            ans=0\n",
    "            for v in quantities:\n",
    "                ans+=(v+x-1)//x\n",
    "            return ans<=n \n",
    "        l=1\n",
    "        r=10**5\n",
    "        while l<r:\n",
    "            mid=(l+r)//2\n",
    "            if check(mid):\n",
    "                r=mid\n",
    "            else:\n",
    "                l=mid+1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "\n",
    "        left, right = 1, max(quantities)\n",
    "\n",
    "        while left <= right:\n",
    "            mid = (left + right) >> 1\n",
    "            if sum((x + mid - 1) // mid for x in quantities) > n:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return left "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        high=max(quantities)\n",
    "        low=1\n",
    "        while low < high:\n",
    "            mid = (low+high)//2\n",
    "            if sum(ceil(q/mid) for q in quantities)<=n:\n",
    "                high=mid\n",
    "            else:\n",
    "                low=mid+1\n",
    "        return low"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        def check(x):\n",
    "            if x == 0:\n",
    "                return False\n",
    "            i = 0\n",
    "            res = 0\n",
    "            for i in quantities:\n",
    "                res += (i + x - 1) // x\n",
    "            return res <= n\n",
    "        l,r = 0, max(quantities)\n",
    "        while l <= r:\n",
    "            mid = l + r >> 1\n",
    "            if check(mid):\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l               "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        left = 1\n",
    "        right = max(quantities)\n",
    "        def f(t):\n",
    "            c = 0\n",
    "            for q in quantities:\n",
    "                c += q // t\n",
    "                if q % t:\n",
    "                    c += 1\n",
    "                if c > n:\n",
    "                    return False\n",
    "            return True\n",
    "        while left <= right:\n",
    "            mid = (left+right) // 2\n",
    "            if f(mid):\n",
    "                right = mid-1\n",
    "            else:\n",
    "                left = mid+1\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "\n",
    "        # 检查是否能小于k\n",
    "        def check(k):\n",
    "            count = 0\n",
    "            for q in quantities:\n",
    "                count += math.ceil(q / k)\n",
    "                if count > n:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        left, right = 1, max(quantities)\n",
    "        while left <= right:\n",
    "            mid = (left + right) >> 1\n",
    "            # check(right + 1) = True\n",
    "            if check(mid):\n",
    "                # 尝试让mid变小\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        \n",
    "        return right + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "\n",
    "        # 检查是否能小于k\n",
    "        def check(k):\n",
    "            count = 0\n",
    "            for q in quantities:\n",
    "                count += math.ceil(q / k)\n",
    "                if count > n:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        left, right = 1, max(quantities)\n",
    "        while left <= right:\n",
    "            mid = (left + right) >> 1\n",
    "            # check(right + 1) = True\n",
    "            if check(mid):\n",
    "                # 尝试让mid变小\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        \n",
    "        return right + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        left, right = 1, max(quantities)\n",
    "        while left < right:\n",
    "            mid = (left+right)//2\n",
    "            tmp = sum((quantitie-1) // mid +1 for quantitie in quantities)\n",
    "            if tmp <= n:\n",
    "                right = mid\n",
    "            else: left = mid+1\n",
    "        return left\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        def check(k):\n",
    "            s = 0\n",
    "            for q in quantities:\n",
    "                s += math.ceil(q / k)\n",
    "            if s <= n:\n",
    "                return True\n",
    "            else:\n",
    "                return False \n",
    "            \n",
    "        lo = max(sum(quantities) // n , 1)\n",
    "        hi = max(quantities) + 1\n",
    "        while lo < hi:\n",
    "            mid = (lo + hi) // 2\n",
    "            if check(mid) == True:\n",
    "                hi = mid \n",
    "            else:\n",
    "                lo = mid + 1 \n",
    "        return lo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "\n",
    "        # 检查是否能小于k\n",
    "        def check(k):\n",
    "            count = 0\n",
    "            for q in quantities:\n",
    "                count += math.ceil(q / k)\n",
    "                if count > n:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        left, right = 1, max(quantities)\n",
    "        while left <= right:\n",
    "            mid = (left + right) >> 1\n",
    "            # check(right + 1) = True\n",
    "            if check(mid):\n",
    "                # 尝试让mid变小\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        \n",
    "        return right + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        def check(x):\n",
    "            if x == 0:\n",
    "                return False\n",
    "            return sum(ceil(v/x) for v in quantities) <= n\n",
    "        return bisect_left(range(1+max(quantities)), True, key=check)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        def check(k):\n",
    "            s = 0\n",
    "            for q in quantities:\n",
    "                s += math.ceil(q / k)\n",
    "            if s <= n:\n",
    "                return True\n",
    "            else:\n",
    "                return False \n",
    "            \n",
    "        lo = 1\n",
    "        hi = max(quantities) + 1\n",
    "        while lo < hi:\n",
    "            mid = (lo + hi) // 2\n",
    "            if check(mid) == True:\n",
    "                hi = mid \n",
    "            else:\n",
    "                lo = mid + 1 \n",
    "        return lo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        def cal(i):\n",
    "            res = 0\n",
    "            for q in quantities:\n",
    "                res += ceil(q/i)\n",
    "            return res  \n",
    "\n",
    "        l, r = 1, max(quantities)\n",
    "        while l <= r:\n",
    "            mid = l + (r-l)//2\n",
    "            temp = cal(mid)\n",
    "            if temp <= n:\n",
    "                r = mid -1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "\n",
    "      def check(x):\n",
    "        count = 0\n",
    "        for q in quantities:\n",
    "            c = q // x\n",
    "            if q % x != 0:\n",
    "                c += 1\n",
    "            count += c\n",
    "        return count > n\n",
    "\n",
    "      lo = 1\n",
    "      li = max(quantities)\n",
    "      while lo < li:\n",
    "          mid = (lo + li) >> 1\n",
    "          if check(mid):\n",
    "              lo = mid + 1\n",
    "          else:\n",
    "              li = mid\n",
    "      return lo\n",
    "      mx = max(quantities)\n",
    "      l = mx//n\n",
    "      r = mx\n",
    "      def check(v):\n",
    "        cnt = 0\n",
    "        for j in quantities:\n",
    "          cnt += (j+v-1)//v\n",
    "          if cnt > n:\n",
    "            return False\n",
    "        return True\n",
    "      while l <= r:\n",
    "        mid = (l+r)//2\n",
    "        if check(mid):\n",
    "          r -= 1\n",
    "        else:\n",
    "          l += 1\n",
    "      return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "\n",
    "\n",
    "        def check(k):\n",
    "            ans = 0\n",
    "            for num in quantities:\n",
    "                ans += math.ceil(num / k)\n",
    "            return ans <= n\n",
    "        \n",
    "        l = 1\n",
    "        r = max(quantities)\n",
    "\n",
    "        # 用二分几？\n",
    "        # 找能满足的最小，用二分1\n",
    "        while l < r:\n",
    "            mid = l + r >> 1\n",
    "            if check(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        \n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        def check(x: int):\n",
    "            cnt = 0\n",
    "            for q in quantities:\n",
    "                cnt += (q-1) // x+1\n",
    "            return cnt <= n\n",
    "        l, r = 1, max(quantities)+1\n",
    "        while l < r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if check(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "\n",
    "        def check(x):\n",
    "            res = 0\n",
    "            for q in quantities:\n",
    "                res += (q + x - 1) // x\n",
    "            return res <= n\n",
    "        l, r = 1, int(1e10)\n",
    "        while l < r:\n",
    "            mid = l + r >> 1\n",
    "            if check(mid): r = mid\n",
    "            else: l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        if len(quantities)==1: return quantities[0]\n",
    "        maxq = max(quantities)\n",
    "        left,right = 1,maxq\n",
    "        res = maxq\n",
    "        def get_valid(mid):\n",
    "            remain = n \n",
    "            for q in quantities:\n",
    "                remain-=math.ceil(q/mid)\n",
    "                # print(mid,)\n",
    "            if remain<0: return False \n",
    "            return True \n",
    "        while(left<=right):\n",
    "            mid  = (left+right)//2 \n",
    "            res1 = get_valid(mid)\n",
    "            if res1:\n",
    "                res = mid \n",
    "                right = mid-1\n",
    "            else:\n",
    "                left = mid+1 \n",
    "        return res \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        def check(x):\n",
    "            cnt = 0\n",
    "            for q in quantities:\n",
    "                if(q % x == 0):\n",
    "                    cnt += q // x\n",
    "                else:\n",
    "                    cnt += q // x + 1\n",
    "            return cnt <= n \n",
    "        left, right = 1, max(quantities)\n",
    "        while(left <= right):\n",
    "            mid = (left + right)//2\n",
    "            if(check(mid)):\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        def check(min_num:int)->bool:\n",
    "            cnt=0\n",
    "            for q in quantities:\n",
    "                cnt += (q-1)//min_num+1\n",
    "            return cnt<=n\n",
    "\n",
    "        left=1\n",
    "        right=max(quantities)+1\n",
    "        while left<right:\n",
    "            mid=left+(right-left)//2\n",
    "            if check(mid):\n",
    "                right=mid\n",
    "            else:\n",
    "                left=mid+1\n",
    "        return left\n",
    "        # def check(x: int) -> bool:\n",
    "        #     # 计算所需商店数量的最小值，并与商店数量进行比较\n",
    "        #     cnt = 0\n",
    "        #     for q in quantities:\n",
    "        #         cnt += (q - 1) // x + 1\n",
    "        #     return cnt <= n\n",
    "        \n",
    "        # l, r = 1, max(quantities) + 1\n",
    "        # # 二分查找寻找最小的使得判定问题为真的 x\n",
    "        # while l < r:\n",
    "        #     mid = l + (r - l) // 2\n",
    "        #     if check(mid):\n",
    "        #         r = mid\n",
    "        #     else:\n",
    "        #         l = mid + 1\n",
    "        # return l\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "\n",
    "        # 检查是否能小于k\n",
    "        def check(k):\n",
    "            count = 0\n",
    "            for q in quantities:\n",
    "                count += math.ceil(q / k)\n",
    "                if count > n:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        left, right = 1, max(quantities)\n",
    "        while left <= right:\n",
    "            mid = (left + right) >> 1\n",
    "            # check(right + 1) = True\n",
    "            if check(mid):\n",
    "                # 尝试让mid变小\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        \n",
    "        return right + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        tot = sum(quantities) \n",
    "        if tot < n:\n",
    "            return 1\n",
    "        l, r = 1, min(max(quantities), tot - (n - 1))\n",
    "        while l <= r:\n",
    "            m = l + r >> 1\n",
    "            s = 0\n",
    "            for x in quantities:\n",
    "                s += (x + m - 1) // m\n",
    "            if s > n:\n",
    "                l = m + 1\n",
    "            else:\n",
    "                r = m - 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        def check(x):\n",
    "            m = 0\n",
    "            for q in quantities:\n",
    "                m += (q + x - 1) // x\n",
    "            return m <= n\n",
    "\n",
    "        l = 1\n",
    "        r = max(quantities)\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if check(mid):\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return r + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "#         sum_=0\n",
    "#         m=len(quantities)\n",
    "#         quantities.sort(reverse=True)\n",
    "#         l=(n-m)*2\n",
    "#         if l<m:\n",
    "#             if l==0:\n",
    "#                 res=quantities[0]\n",
    "#             else:\n",
    "#                 for i in range(l):\n",
    "#                     sum_+=i\n",
    "#                 res=max(math.ceil(sum_/l),quantities[l])\n",
    "#         else:\n",
    "#             for num in quantities:\n",
    "#                 sum_+=num\n",
    "#             res=math.ceil(sum_/n)\n",
    "#         return res\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        # 判定问题\n",
    "        def check(x: int) -> bool:\n",
    "            # 计算所需商店数量的最小值，并与商店数量进行比较\n",
    "            cnt = 0\n",
    "            for q in quantities:\n",
    "                cnt += (q - 1) // x + 1\n",
    "            return cnt <= n\n",
    "        \n",
    "        l, r = 1, max(quantities) + 1\n",
    "        # 二分查找寻找最小的使得判定问题为真的 x\n",
    "        while l < r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if check(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        left, right = 1, max(quantities)\n",
    "        while left < right:\n",
    "            mid = left + (right-left)//2\n",
    "            total = 0\n",
    "            for i in quantities:\n",
    "                if i % mid == 0:\n",
    "                    total += i//mid\n",
    "                else:\n",
    "                    total += i//mid + 1\n",
    "            \n",
    "            if total > n:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid \n",
    "        \n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        left = 1\n",
    "        right = max(quantities) + 1\n",
    "\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            seq = 0\n",
    "            for i in quantities:\n",
    "                seq += math.ceil(i / mid)\n",
    "            if seq > n:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        \n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        l, r = 0, max(quantities) + 1\n",
    "        while l + 1 < r:\n",
    "            m = (l + r)//2\n",
    "            if sum((x + m - 1) // m for x in quantities) <= n:\n",
    "                r = m\n",
    "            else:\n",
    "                l = m\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        sums = sum(quantities)\n",
    "        def check(maxnum):\n",
    "            n_left = n\n",
    "            if maxnum*n < sums:\n",
    "                return False\n",
    "            \n",
    "            for i in quantities:\n",
    "                n_left-=i//maxnum if i%maxnum==0 else i//maxnum + 1\n",
    "                \n",
    "            return n_left >= 0\n",
    "\n",
    "        print(check(10))\n",
    "        l,r = 1,max(quantities)+1\n",
    "        while l < r:\n",
    "            mid = (l+r)//2\n",
    "            if check(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BinarySearch:\n",
    "    def __init__(self):\n",
    "        return\n",
    "\n",
    "    @staticmethod\n",
    "    def find_int_left(low: int, high: int, check: Callable) -> int:\n",
    "        # 模板: 整数范围内二分查找，选择最靠左满足check\n",
    "        while low < high - 1:\n",
    "            mid = low + (high - low) // 2\n",
    "            if check(mid):\n",
    "                high = mid\n",
    "            else:\n",
    "                low = mid\n",
    "        return low if check(low) else high\n",
    "\n",
    "    @staticmethod\n",
    "    def find_int_right(low: int, high: int, check: Callable) -> int:\n",
    "        # 模板: 整数范围内二分查找，选择最靠右满足check\n",
    "        while low < high - 1:\n",
    "            mid = low + (high - low) // 2\n",
    "            if check(mid):\n",
    "                low = mid\n",
    "            else:\n",
    "                high = mid\n",
    "        return high if check(high) else low\n",
    "\n",
    "    @staticmethod\n",
    "    def find_float_left(low: float, high: float, check: Callable, error=1e-6) -> float:\n",
    "        # 模板: 浮点数范围内二分查找, 选择最靠左满足check\n",
    "        while low < high - error:\n",
    "            mid = low + (high - low) / 2\n",
    "            if check(mid):\n",
    "                high = mid\n",
    "            else:\n",
    "                low = mid\n",
    "        return low if check(low) else high\n",
    "\n",
    "    @staticmethod\n",
    "    def find_float_right(low: float, high: float, check: Callable, error=1e-6) -> float:\n",
    "        # 模板: 浮点数范围内二分查找, 选择最靠右满足check\n",
    "        while low < high - error:\n",
    "            mid = low + (high - low) / 2\n",
    "            if check(mid):\n",
    "                low = mid\n",
    "            else:\n",
    "                high = mid\n",
    "        return high if check(high) else low\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        \n",
    "        def check(x):\n",
    "            return sum(math.ceil(num/x) for num in quantities) <= n\n",
    "        \n",
    "        return BinarySearch().find_int_left(1, max(quantities), check)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        import math\n",
    "        left = 0\n",
    "        right = max(quantities)\n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2\n",
    "            value = sum([math.ceil(x/mid) for x in quantities])\n",
    "            if value <= n:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid\n",
    "        return right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        def valid(k):\n",
    "            return sum([ceil(q/k) for q in quantities]) <= n\n",
    "\n",
    "        l = 1\n",
    "        r = max(quantities) + 1\n",
    "        while l < r:\n",
    "            mid = (l+r)//2\n",
    "            if valid(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities) -> int:\n",
    "        if n == len(quantities):\n",
    "            return max(quantities)\n",
    "        left, right = 1, 10**5\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            cur = sum([math.ceil(q/mid) for q in quantities])\n",
    "            # print(n, cur, left, right, mid)\n",
    "            if cur > n:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        # print(n, cur, left, right, mid)\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        left, right = 1,100000\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if sum([math.ceil(q / mid) for q in quantities]) <= n:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        right = sum(quantities)\n",
    "        left = 1\n",
    "    \n",
    "        while left<= right:\n",
    "            mid = (left+right)>>1\n",
    "            \n",
    "            if sum([(num+mid-1)//mid for num in quantities])>n:\n",
    "                left = mid+1\n",
    "            else:\n",
    "                right = mid-1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities) -> int:\n",
    "        return bisect_left(range(1, ceil(5 * sum(quantities) / n) + 1), 1, key=lambda x: sum(ceil(y / x) for y in quantities) <= n) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        right = sum(quantities)\n",
    "        left = (right//n)\n",
    "        while left<= right:\n",
    "            mid = (left+right)>>1\n",
    "            if mid ==0:\n",
    "                return 1\n",
    "            if sum([(num+mid-1)//mid for num in quantities])>n:\n",
    "                left = mid+1\n",
    "            else:\n",
    "                right = mid-1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        def check(k):\n",
    "            check=0\n",
    "            for num in quantities:\n",
    "                check+=(num-1)//k+1\n",
    "            if check<=n:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        if check(1) is True:\n",
    "            return 1\n",
    "        l=1\n",
    "        h=max(quantities)\n",
    "        while h-l>1:\n",
    "            m=(l+h)//2\n",
    "            if check(m) is True:\n",
    "                h=m\n",
    "            else:\n",
    "                l=m\n",
    "        return h"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizedMaximum(self, n: int, quantities: List[int]) -> int:\n",
    "        l, r = 1, max(quantities)\n",
    "        while l <= r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if check(quantities, n, mid):\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l\n",
    "\n",
    "# 判断是否可以分给n个商店\n",
    "# 如果小于等于 说明还可以减小num 每个商店少分配 让更多的商店装到\n",
    "def check(quantities, n, num):\n",
    "    cnt = sum([ceil(quantity / num) for quantity in quantities])\n",
    "    return cnt <= n\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
